//
//  ProblemMS0201.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/23.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 面试题 02.01. 移除重复节点
 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

 示例1:
      输入：[1, 2, 3, 3, 2, 1]
      输出：[1, 2, 3]
 示例2:
      输入：[1, 1, 1, 1, 2]
      输出：[1, 2]
 提示：
     链表长度在[0, 20000]范围内。
     链表元素在[0, 20000]范围内。
 进阶：
    如果不得使用临时缓冲区，该怎么解决？
 */
@objcMembers class ProblemMS0201: NSObject {
    func solution() {
        let root = ListNode(1)
        root.next = ListNode(2)
        root.next?.next = ListNode(3)
        root.next?.next?.next = ListNode(3)
        root.next?.next?.next?.next = ListNode(2)
        root.next?.next?.next?.next?.next = ListNode(1)
        
        let node = removeDuplicateNodesClear(root)
        printNode(node)
    }
    
    /*
     哈希
     创建一个map存储链表的值，发现哈希中存储了，就删除这个节点
     */
    func removeDuplicateNodes(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        var map:[Int: Int] = [head!.val : 1]
        var node = head
        while node?.next != nil {
            if map[node!.next!.val] != nil {
                node?.next = node?.next?.next
            } else {
                map[node!.next!.val] = 1
                node = node?.next
            }
        }
        return head
    }
    
    /*
     不使用缓冲区：双层循环，时间换空间
     */
    func removeDuplicateNodesClear(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        var node = head
        while node != nil {
            var sNode = node
            
            while sNode?.next != nil {
                if sNode!.next!.val == node!.val {
                    sNode?.next = sNode?.next?.next
                } else {
                    sNode = sNode?.next
                }
            }
            node = node?.next
        }
        
        return head
    }
}
